#include<iostream>

using namespace std;

template<class T>
class Queue
{
private:
	class Node
	{
	public:
		T _value;
		Node* _prev;
		Node* _next;
		Node()
			:_value(T())
			,_prev(nullptr)
			,_next(nullptr)
		{}
		Node(T value)
			:_value(value)
			, _prev(nullptr)
			, _next(nullptr)
		{}
	};
public:
	Queue()
	{
		_head = nullptr;
		_tail = nullptr;
		size = 0;
	}
	~Queue()
	{
		Node* cur = _head;
		while (cur != nullptr)
		{
			_head = _head->_next;
			delete cur;
			cur = _head;
		}
	}
	//打印
	void printQueue()
	{
		if (empty())
		{
			cout << "Queue is nullptr" << endl;
			return;
		}
		cout << "Queue->";
		Node* cur = _head;
		while(cur != nullptr)
		{
			cout << "->" << cur->_value;
			cur = cur->_next;
		}
		cout << endl;
	}
	//入队
	void enqueue(T data) 
	{
		Node* newnode = new Node(data);
		if (empty())
		{
			_head = newnode;
			_tail = newnode;
		}
		else
		{
			newnode->_prev = _tail;
			_tail->_next = newnode;
			_tail = newnode;
		}
		size++;
	}

	//出队列
	T dequeue() 
	{
		if (empty())
		{
			throw std::out_of_range("队列为空，无法获取队首元素");
		}
		Node* cur = _head;
		T value = cur->_value;
		_head = _head->_next;
		if (_head == nullptr)
		{
			_tail = nullptr;
		}
		else
		{
			_head->_prev = nullptr;
		}
		delete cur;
		size--;
		return value;
	}

	
	T& front() {
		if (empty())
		{
			throw std::out_of_range("队列为空，无法获取队首元素");
		}
		return _head->_value;
	}

	//判断为空
	bool empty() {
		return size == 0;
	}
	
private:
	Node* _head;
	Node* _tail;
	int size;
};

int main()
{
	Queue<char> q;
	q.enqueue('a');
	q.printQueue();

	q.enqueue('b');
	q.printQueue();

	q.enqueue('c');
	q.printQueue();

	q.dequeue();
	q.printQueue();

	q.dequeue();
	q.printQueue();

	q.dequeue();
	q.printQueue();
}
